// 1504. 统计全 1 子矩形

function numSubmat(mat: number[][]): number {
    const row = mat.length
    if(row==0) return 0
    const col = mat[0].length
    let ans = 0
    // 保存每个位置到现在有多少个连续的1
    const cnt = new Array(row).fill(0).map(e=>new Array(col).fill(0))
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            if(j==0) cnt[i][j] = mat[i][j]
            else if(mat[i][j]==1) cnt[i][j] = cnt[i][j-1]+1
        }
    }
    // 统计
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            let min = cnt[i][j]
            ans+=min
            for(let t=i-1;t>=0;t--){
                min = Math.min(min,cnt[t][j])
                ans+= (t-i+1)*min
            }
        }
    }

    return ans
};

/**
 * 单调栈优化
 * 因为存在着（0，2） （1，2） （2，2）这种要返回向前遍历找min的情况
 * 单调栈正好就是可以针对这种情况进行优化
 */

 